1. Field of the Invention
This invention relates to digital data processing systems and, in particular, to a Fourier transform processor using incremental processing means and methods.
2. Description of the Prior Art
Digital data processors and, in particular, digital Fourier transform processors are conventionally implemented as whole-number processing devices either in software with a general purpose digital computer in firmware with a micro-programmable processor, or with special purpose hardwired logic. A digital filter is conventionally implemented with sum-of-the-products computations, where array multiplier integrated circuits are used to provide whole-number multiplication capability. Whole-number multiplication circuitry is complex and expensive and therefore has only been qualified as time-shared arithmetic circuitry for sequential processing architecture. Such sequential processing is relatively slow, where a single complex (real and imaginary) multiplication operation may be performed in a microsecond with conventional type higher speed processors and where 2,304 complex multiply operations must be performed in sequence to implement a 512-point FFT, representing 2.3 milliseconds per FFT computation for higher speed conventional FFT processors. This rate is adequate for many applications but has precluded processing of signals at microwave sampling rates.
Fourier processors can be implemented in many forms including the discrete Fourier transform (DFT) and the fast Fourier transform (FFT) implemented with digital electronics, spectrum analyzers implemented with analog electronics, illumination processors implemented with analog electro-optics, and acoustical processors implemented with analog surface acoustic wave (SAW) devices. The analog illumination and analog acoustical processors are the highest speed and lowest cost devices, followed by the analog electronic processors and then by the digital electronic processors.
Digital processors have the lowest speed and highest cost, but digital processors have a major advantage, high resolution. Digital processors have virtually unlimited resolution; which extrapolates into high accuracy, high dynamic range, and high signal-to-noise-ratio (SNR) enhancement.
Although input signals are typically analog and are therefore limited to a resolution of about one-part-per-thousand, precision is significantly enhanced with processing gain inherent in Fourier transformation. Processing gain can be further enhanced almost without limit with coherent integration-after-transformation. Therefore, a digital transform processor generates high accuracy output information such as 20-bit (one-part-per-million) output information from low accuracy input information such as 7-bit (one-part-per-hundred) input information with Fourier transform and integration processing gain.
Analog filtering technologies achieve enhanced accuracy through processing gain, but analog processing precludes accuracy beyond a practical limit which is typically 10-bits (one-part-per-thousand). Therefore, the analog technologies are severely limited and can only be used for low accuracy applications.
FFT processors are universally implemented with complex (real and imaginary) multiply operations, where each complex multiply together with auxiliary processing operations is called a "butterfly" operation because of the appearance on an FFT diagram. Just as with conventional processors, the processor of the present invention can implement an FFT with conventional interconnection of butterfly operations.
Programmable FFT processors presently dominate the market. General purposes (GP) stored program computers are widely used for low speed FFT requirements when the processor is time-shared for both general purpose and FFT processing requirements. Special purpose (SP) microprogrammable array transform processors are widely used for higher speed FFT requirements. These SP processors may be 100-times faster than the GP processors, but they typically operate in conjunction with a GP host processor for GP processing capability. GP processors and SP processors both operate on a parallel word, sequential computation basis. Each butterfly operation is synthesized with four multiply and four addition operations and with various overhead operations in sequence. The FFT is then synthesized with all butterfly operations processed in sequence. This sequential operation of programmable FFT processors significantly reduces speed.